/**
 * FileName: Exercise1931.c
 * --------------------------------------------------------------------------------------------------------------------
 * 19.31 Draw the DFS forest that results from a standard adjacency-lists DFS of the digraph
    ```txt
    3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
    ```
 */
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//顶点相关
typedef struct node* link;
struct node {
    int v;
    link next;
};

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    link* adj;
};

#define dfsR2 search
static int cnt;
static int* pre;
//Program 19.2 新增cntP、数组post
static int cntP;
static int* post;

static int depth;

//辅助函数声明
void HELPinit(int);
void HELPcleanUp();
void show(char*, Edge);
link NEW(int, link);
Edge EDGE(int, int);
void GRAPHshow(Graph);
void dfsR(Graph, Edge);
void dfsR2(Graph, Edge);
void printIndent();

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);
void GRAPHsearch(Graph);
void GRAPHsearch2(Graph, int);

//辅助函数实现
void HELPinit(int maxV) {
    //全局变量初始化
    int v;
    cnt = 0;
    pre = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        pre[v] = -1;
    }
    depth = 0;

    cntP = 0;
    post = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        post[v] = -1;
    }
}

void HELPcleanUp() {
    free(pre);
    free(post);
}

link NEW(int v, link next) {
    link x = (link) malloc(sizeof(*x));
    x->v = v;
    x->next = next;
    return x;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    printf("%d vertices, %d edges\n", G->V, G->E);
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        printf("%2d:", v);
        for (t = G->adj[v]; t != NULL; t = t->next) {
            printf(" %2d", t->v);
        }
        printf("\n");
    }
}

void show(char* key, Edge e) {
    printIndent();
    printf("%d-%d %s\n", e.v, e.w, key);
}

/**
 * Program 19.2 DFS of a digraph
 * ---------------------------------------------------------------------------------------------------------------------
 * This DFS function for digraphs represented with adjacency lists is instrumented to show the role that
 * each edge in the graph plays in the DFS.
 *
 * It assumes that Program 18.3 is augmented to declare and initialize the array `post` and
 * the counter `cntP` in the same way as `pre` and `cnt`, respectively.
 *
 * See Figure 19.10 for sample output and a discussion about implementing show.
 *
 */
void dfsR(Graph G, Edge e) {
    // link t;
    // int w = e.w;
    // pre[w] = cnt++;
    // for (t = G->adj[w]; t != NULL; t = t->next) {
    //     if (pre[t->v] == -1) {
    //         // w指向t->v的边 tree link
    //         dfsR(G, EDGE(w, t->v));
    //     }else if (t->v == e.v) {
    //         // w指向t->v的边 parent link
    //     }else if (pre[w] > pre[t->v]) {
    //         // w指向t->v的边 back link
    //     }else if (pre[w] < pre[t->v]) {
    //         // w指向t->v的边 down link
    //     }
    // }

    link t;
    int v;
    int w = e.w;
    Edge x;
    pre[w] = cnt++;
    for (t = G->adj[w]; t != NULL; t = t->next) {
        if (pre[t->v] == -1) {
            // w指向t->v的边 tree link
            dfsR(G, EDGE(w, t->v));
        }else {
            v = t->v;
            x = EDGE(w, v);
            if (post[v] == -1) {
                // w指向t->v的边 back link
                // show("back", x);
            }else if (pre[v] > pre[w]) {
                // w指向t->v的边 down link
                // show("down", x);
            }else {
                // w指向t->v的边 cross link
                // show("cross", x);
            }
        }
    }
    post[w] = cntP++;

}

/**
 * Program 19.2 DFS of a digraph
 * ---------------------------------------------------------------------------------------------------------------------
 * This DFS function for digraphs represented with adjacency lists is instrumented to show the role that
 * each edge in the graph plays in the DFS.
 *
 * It assumes that Program 18.3 is augmented to declare and initialize the array `post` and
 * the counter `cntP` in the same way as `pre` and `cnt`, respectively.
 *
 * See Figure 19.10 for sample output and a discussion about implementing show.
 *
 */
void dfsR2(Graph G, Edge e) {
    link t;
    int v;
    int w = e.w;
    Edge x;
    show("tree", e);
    depth++;
    pre[w] = cnt++;
    for (t = G->adj[w]; t != NULL; t = t->next) {
        if (pre[t->v] == -1) {
            // w指向t->v的边 tree link
            dfsR2(G, EDGE(w, t->v));
        }else {
            v = t->v;
            x = EDGE(w, v);
            if (post[v] == -1) {
                show("back", x);
            }else if (pre[v] > pre[w]) {
                show("down", x);
            }else {
                show("cross", x);
            }
        }
    }
    post[w] = cntP++;
    depth--;
}

void printIndent() {
    int i;
    for (i = 0; i < depth; i++) {
        printf("  "); // 每层缩进2个空格
    }
}

//图操作函数实现
Graph GRAPHinit(int V) {
    int v;
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = (link*) malloc(V * sizeof(link));
    for (v = 0; v < V; v++) {
        G->adj[v] = NULL;
    }
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    G->adj[v] = NEW(w, G->adj[v]);
    G->E++;
}

void GRAPHremoveE(Graph G, Edge e) {
    link x1;
    link t1;
    int v = e.v;
    int w = e.w;

    //从v的邻接列表里找到w，删除该节点
    t1 = G->adj[v];
    while (t1 != NULL) {
        if (t1->v == w) {
            break;
        }
        x1 = t1;
        t1 = t1->next;
    }
    if (t1 == NULL) {
        return;
    }
    if (x1 == NULL) {
        //说明w是首节点
        G->adj[v] = t1->next;
    }else {
        x1->next = t1->next;
    }

    free(t1);
    G->E--;
}
int GRAPHedges(Edge a[], Graph G) {
    int E = 0;
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        for (t = G->adj[v]; t != NULL; t = t->next) {
            a[E++] = EDGE(v, t->v);
        }
    }

    return E;
}
Graph GRAPHcopy(Graph G) {
    Graph copy = GRAPHinit(G->V);
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        for (t = G->adj[v]; t != NULL; t = t->next) {
            GRAPHinsertE(copy, EDGE(v, t->v));
        }
    }

    return copy;

}
void GRAPHdestroy(Graph G) {
    int v;
    for (v = 0; v < G->V; v++) {
        link t = G->adj[v];
        while (t != NULL) {
            link next = t->next;
            free(t);
            t = next;
        }
    }
    free(G->adj);
    free(G);
}

void GRAPHsearch(Graph G) {
    int v;
    HELPinit(G->V);
    for (v = 0; v < G->V; v++) {
        if (pre[v] == -1) {
            search(G, EDGE(v,v));
        }
    }
}

void GRAPHsearch2(Graph G, int s) {
    int v = s;
    HELPinit(G->V);
    printf("DFS forest: %d as start vertex\n", s);
    int count = 0;
    while (count < G->V) {
        if (pre[v] == -1) {
            search(G, EDGE(v,v));
        }
        v++;
        v=v%G->V;
        count++;

    }
    printf("------------------------------------------------------------\n");
}

//测试函数声明
void test_dfs_forest();

int main(int argc, char *argv[]) {
    test_dfs_forest();
    return 0;
}

//测试函数实现
void test_dfs_forest() {
    int V = 10;
    Graph G = GRAPHinit(V);

    GRAPHinsertE(G, EDGE(3, 7));
    GRAPHinsertE(G, EDGE(1, 4));
    GRAPHinsertE(G, EDGE(7, 8));
    GRAPHinsertE(G, EDGE(0, 5));
    GRAPHinsertE(G, EDGE(5, 2));
    GRAPHinsertE(G, EDGE(3, 8));
    GRAPHinsertE(G, EDGE(2, 9));
    GRAPHinsertE(G, EDGE(0, 6));
    GRAPHinsertE(G, EDGE(4, 9));
    GRAPHinsertE(G, EDGE(2, 6));
    GRAPHinsertE(G, EDGE(6, 4));

    // GRAPHshow(G);
    int s;
    for (s = 0; s < G->V; s++) {
        GRAPHsearch2(G, s);
    }
    HELPcleanUp();
}